package club.babyf.nativeai.demo.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * RestoreIPAddress.
 *
 * @author zhanglei.
 * @date 2025/4/8 09:25.
 * @description 恢复IP地址.
 */
public class _2_RestoreIPAddress {

    List<String> res = new ArrayList<>();

    List<String> path = new ArrayList<>();

    public List<String> restoreIPAddress(String s) {
        backTracking(s, 0);
        return res;
    }

    private void backTracking(String s, int startIdx) {
        if (path.size() == 4 && s.length() == startIdx) {
            res.add(String.join(".", path));
            return;
        }

        for (int i = startIdx; i < s.length() && i - startIdx <= 3; i++) {
            if (i > startIdx && s.charAt(startIdx) == '0') {
                return;
            }

            String substring = s.substring(startIdx, i + 1);
            int v = Integer.parseInt(substring);
            if (v >= 0 && v <= 255) {
                path.add(substring);
                backTracking(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        _2_RestoreIPAddress restoreIPAddress = new _2_RestoreIPAddress();
        List<String> strings = restoreIPAddress.restoreIPAddress("25525511123");
        System.out.println(strings);
    }

}
